package com.mystudy.leetcode.problem.tree.p_270;

import com.mystudy.leetcode.base.TreeNode;
import com.mystudy.leetcode.base.TreeNodeUtils;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 最接近的二叉搜索树值
 * @author: zhouzhilong
 * @create: 2019-08-09 17:58
 **/

/**
 * 给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。
 *
 * 注意：
 *
 * 给定的目标值 target 是一个浮点数
 * 题目保证在该二叉搜索树中只会存在一个最接近目标值的数
 * 示例：
 *
 * 输入: root = [4,2,5,1,3]，目标值 target = 3.714286
 *
 *     4
 *    / \
 *   2   5
 *  / \
 * 1   3
 *
 * 输出: 4
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {
        TreeNode root = TreeNodeUtils.generateTwoTrees(new Integer[]{1,null,2});
        int result = closestValue(root, 3.714286);
        LOGGER.debug("result = [{}]",result);
    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]",cost);
    }



    private double min = Double.MAX_VALUE;
    private int value = 0 ;
    public int closestValue(TreeNode root, double target) {
        close(root,target);
        return value;
    }
    private void close(TreeNode root,double target){
        if(root == null){
            return;
        }
        double m = root.val - target;
        double dis = Math.abs(m);
        if(dis < min){
            min = dis;
            value = root.val;
        }
        if(m >0){
            //说明节点的值大于指定的值，那么节点的右孩子都比节点大，所以最接近目标值的数必然不会在右子树
            close(root.left,target);
        }else{
            close(root.right,target);
        }
    }


}
